//
// Created by Luhang on 2023/5/29/029.
//

#ifndef INC_0520_BITSET_H
#define INC_0520_BITSET_H

#endif //INC_0520_BITSET_H

#pragma once

#include <iostream>
#include <vector>
#include <string>
#include <ctime>
using namespace std;

template<size_t N>
class bitset{
public:
    bitset(){
        _bits.resize(N/8 + 1, 0);
    }

    void set(size_t x){
        size_t i = x / 8;
        size_t j = x % 8;
        _bits[i] |= (1 << j);
    }

    void reset(size_t x){
        size_t i = x / 8;
        size_t j = x % 8;
        _bits[i] &= ~(1 << j);
    }

    bool test(size_t x){
        size_t i = x / 8;
        size_t j = x % 8;
        return _bits[i] & (1 << j);
    }

private:
    vector<char> _bits;
};

void test_bitset1(){
    bitset<100> bs;
    bs.set(6);
    bs.set(8);
    bs.set(9);
    cout << bs.test(9) << endl;
    cout << bs.test(6) << endl;

    bs.reset(9);
    cout << bs.test(9) << endl;
    cout << bs.test(6) << endl;
}

template<size_t N>
class twoBitset{
public:
    void set(size_t x){
        if (_bs1.test(x) == false && _bs2.test(x) == false)
            _bs2.set(x);
        else if (_bs1.test(x) == false && _bs2.test(x) == true){
            _bs1.set(x);
            _bs2.reset(x);
        }
    }

    void Print(){
        for (int i = 0; i < N; ++i) {
            if (_bs2.test(i))
                cout << i << endl;
        }
    }

private:
    bitset<N> _bs1;
    bitset<N> _bs2;
};

void test_twoBitset()
{
    int a[] = { 3, 45, 53, 32, 32, 43, 3, 2, 5, 2, 32, 55,43};
    twoBitset<100> bs;
    for (auto e : a)
    {
        bs.set(e);
    }
    bs.Print();
}

struct BKDRHash{
    size_t operator()(const string& s){
        size_t hash = 0;
        for (auto ch : s){
            hash += ch;
            hash *= 31;
        }

        return hash;
    }
};

struct APHash{
    size_t operator()(const string& s){
        size_t hash = 0;
        for (long i = 0; i < s.size(); i++){
            size_t ch = s[i];
            if ((i & 1) == 0)
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            else
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
        }
        return hash;
    }
};


struct DJBHash{
    size_t operator()(const string& s){
        size_t hash = 5381;
        for (auto ch : s){
            hash += (hash << 5) + ch;
        }
        return hash;
    }
};

template<size_t N, class K = string , class Hash1 = BKDRHash, class Hash2 = APHash, class Hash3 = DJBHash>
class BloomFilter{
public:
    void set(const K& key){
        size_t len = N * _x;
        size_t hash1 = Hash1()(key) % len;
        _bs.set(hash1);
        size_t hash2 = Hash2()(key) % len;
        _bs.set(hash2);
        size_t hash3 = Hash3()(key) % len;
        _bs.set(hash3);
    }

    bool test(const K& key){
        size_t len = N * _x;

        size_t hash1 = Hash1()(key) % len;
        if (!_bs.test(hash1))
        {
            return false;
        }

        size_t hash2 = Hash2()(key) % len;
        if (!_bs.test(hash2))
        {
            return false;
        }

        size_t hash3 = Hash3()(key) % len;
        if (!_bs.test(hash3))
        {
            return false;
        }

        return true;
    }

private:
    static const size_t _x = 6;
    bitset<N * _x> _bs;
};

void test_BloomFilter1()
{
    int x1{666};
    cout << x1 << endl;

    BloomFilter<100> bs;
    bs.set("sort");
    bs.set("bloom");
    bs.set("hello world hello bit");
    bs.set("test");
    bs.set("ate");

    cout << bs.test("sort") << endl;
    cout << bs.test("bloom") << endl;
    cout << bs.test("hello world hello bit") << endl;
    cout << bs.test("ate") << endl;
    cout << bs.test("test") << endl;
    cout << bs.test("tors") << endl;
}